The present invention relates to a method for decoding double-encoding codes and an apparatus using the same, and in particular, to an erasure correcting method and an apparatus using the same.
In communication and computer systems, there have been widely utilized error correcting codes for the purpose of the system reliability. Based on the error detecting codes, the transmitted information is checked whether or not the predetermined rules imposed thereon are satisfied. If it is found that the rules are satisfied, the information is determined to be free of errors. On the contrary, if the rules are not satisfied for the information, the system assumes that an error has been found and requests to retransmit the information, or the error is automatically corrected by use of the error correcting codes on a device for receiving the transmitted information. A Galois field has been utilized to execute such operations for detecting and correcting errors.
Recently, error correcting codes have been adopted in a PCM recording system in which audio and video signals are digitized before they are recorded.
To implement a higher error correction capability, there is a system utilizing codes with long lengths in which each code is constituted by duplicatedly encoding two kinds of codes having rather simple structure (these codes may be of the same kind). This provision allows to decode the code through two stages, hence the decoding algorithm can be advantageously simplified as compared with that used when a code which has a long code length and a high error correction capability is decoded at a time. Furthermore, these codes can be effectively processed with respect to both the burst and random errors.
The double-encoding codes include the product, concatenated, and cross interleaved codes. Among various methods for decoding double-encoding codes, the following two decoding methods are commonly used.
(a) A decoder of the first stage possesses at least an error detecting function. When the decoder detects an error in a first data, it adds an erasure flag to all symbols constituting the first data in which the error is found, thereby setting the erasure symbols. A decoder of the second stage corrects the errors in a second data based on the positional information of the erasure symbols supplied from the decoder of the first stage (erasure correcting method).
(b) The decoders of the first and second stages independently perform the respective error detecting and correcting functions. Especially, the erasure correcting method of (a) develops a practical error correction capability and requires only a simple hardware designing; therefore, it has been widely applied to the devices such as a digital audio disk (DAD) and a digital video tape recorder (DVTR).
Let us consider now the Reed-Solomon codes (to be referred to as RS codes herebelow) shown in FIG. 2 illustrating double-encoding codes, that is, product codes. Assume that a first data along the row direction is A code and that a second data along the column direction is B code. The A code is decoded together with an error detection or an error detection and correction. When an error is detected in a decode operation of the A code, an erasure flag is added to all symbols of the first data arranged in the row direction so as to generate the erasure symbols. When the B code is decoded, the erasure correction is effected by use of the erasure symbol positional information resulted from the operation to decode the A code.
For an RS (n, k) code whose code length and number of information points are n and kv, respectively, the minimum distance is represented to be n-k+1, so the number of erasure symbols that can be corrected is n-k at the maximum. The parity check matrix of this code is given by expression (1), where .alpha. represents the primitive root of a Galois field GF (q.sup.m) and the code length n is a positive integer not exceeding q.sup.m -1. ##EQU1##
Assuming the code word vector, error vector, and receive vector to be =(v.sub.1, v.sub.2, . . . , v.sub.n), =(e.sub.1, e.sub.2, . . . , e.sub.n), and =(r.sub.1, r.sub.2, . . . , r.sub.n), respectively, then the following expression is obtained. EQU - + (2)
Then, syndrome =(S.sub.1, S.sub.2, . . . , S.sub.n-k) is defined in terms of the parity check matrix and the receive vector as follows. ##EQU2## where .sup.T and .sup.T represent the transposed matrices of and , respectively.
Assume that the positions of the erasure symbols which are l in number with l not exceeding n-k are represented as a1, a2, . . . , al and that the magnitudes of the errors associated therewith are expressed as E.sub.a1, E.sub.a2, . . . , E.sub.al, then there exists the following relationships between the syndromes and the magnitudes of the errors. ##EQU3##
The syndrome =(S.sub.1, S.sub.2, . . . , S.sub.l) and the erasure symbol positions a1, a2, . . . , al are known in expression (4), hence the magnitudes of the errors E.sub.a1, E.sub.a2, . . . , E.sub.al can be obtained from expression (4) as follows. ##EQU4## where, [ ].sup.-1 represents the inverse matrix of the matrix [ ]. As a consequence, in the l erasure correcting method conventionally utilized to correct errors which are l in number, a circuit for solving the l-order matrix equation of expression (5) must be implemented by hardware including ROM's and logic gates.
The following paragraphs describe a concrete conventional example in which an RS (n.sub.H =39 , k.sub.H =36) code and an RS (n.sub.V =31, k.sub.V =28) code in a Galois field GF (2.sup.8) are used as the A and B codes, respectively.
Assume that a decoder of the A code has at least the function to detect an error and that when an error is detected, erasure flags are added to the first data in order to create erasure symbols. A decoder of the B code can perform the erasure correction on symbols which are n.sub.V -k.sub.V =31-28=3 in number at the maximum. The following two examples will be explained: (1) Two erasure correcting method in which the erasure correction is conducted if the number of erasure symbols is at most two and the error is detected if the number is at least three, and (2) Three erasure correcting method in which the erasure correction is carried out if the number of erasure symbols is at most three and the error is detected if the number is at least four.